Subject: PRSP Reduction

From: [email-masked] (Paul Brittain)
Date: Wed, 1 Jun 94 12:30:13 BST

Peter,

Sorry I did not make our proposal for PRSP reduction sufficiently clear -
English is rarely both precise and concise!

The difference between my thoughts and your subsequent mail is that I did not
intend to require the receiver to wait until an ADDITIONAL half-window
of frames had been passed before sending the PRSP, but only that he wait until
the half-window point is reached.

The logic I had envisaged was as follows (omitting inc/dec window logic):

    IF frame marked PREQ THEN
      Flag PREQ received for current window
      (do whatever the Receiver needs to increase/decrease the window size)
    ENDIF
    Forward frame to local LAN
    IF number of frames received >= half-window point AND PREQ flag set THEN
      Request resources for new window
    ENDIF
    IF got resources for new window (could be an asynchronous event) THEN
      Send PRSP to start next window
      Reset PREQ received flag
    ENDIF

Compare this with the logic from your mail:

>     if ((# messages received in the previous window, including the
>         previous but not the current PREQ) <= (1/2 the current NWS))
>     then
>       send the PRSP after I have received ((1/2 the NWS)-1) more
>           messages
>     else
>       send the PRSP as soon as I have sufficient resources for the
>           window I am granting

As always, a diagram is clearer - though we actually need to look at 4 cases.
At the top of each diagram the sender receives the PRSP that initiates flow on
a circuit.

Note that in all these diagrams I have labelled the frames with the number that
each side views the frame as representing within the current window.  In the
more complex cases this will differ between sender and receiver of the pacing.

Case 1:  Idle link
==================

This is when we really want to reduce the PRSP traffic.

Assume the round-trip delay is much less than the inter-frame gap.  The
receiver could choose to decrease the window size in this situation, but this
is not shown below so as to enable better comparison with the later examples.

                Sender                                  Receiver
                ======                                  ========
                PRSP
                <-----------------------------------------------
 Frame 1                                          Frame 1 + PREQ     Frame 1
 --------------->---------------------------------------------->---------->

 Frame 2                                               Frame 2       Frame 2
 --------------->---------------------------------------------->---------->

 Frame 3                                               Frame 3       Frame 3
 --------------->---------------------------------------------->---------->

 Frame 4                                               Frame 4       Frame 4
 --------------->---------------------------------------------->---------->
                                                               |
                PRSP                                           |
                <-----------------------------------------------

                etc.....  (steady state reached)

Case 2:  Sender using < half-window
===================================

Now let's make the link a bit slower relative to the gap between frames so that
the sender uses more of the available window.  Remember that the frames are
numbered according to their perceived position within the current window rather
than simply to denote frame contents.

In this example, NWS=8 and the PRSP crosses with 2 frames because of round-trip
delay.

                Sender                                  Receiver
                ======                                  ========
                PRSP
                <-----------------------------------------------
 Frame 1                                          Frame 1 + PREQ     Frame 1
 --------------->---------------------------------------------->---------->

 Frame 2                                               Frame 2       Frame 2
 --------------->---------------------------------------------->---------->

 Frame 3                                               Frame 3       Frame 3
 --------------->---------------------------------------------->---------->

 Frame 4                                               Frame 4       Frame 4
 --------------->---------------------------------------------->---------->
                                                               |
                                                               |
                                    ----------------------------
                                    |
 Frame 5                            |                  Frame 1       Frame 1
 --------------->---------------------------------------------->---------->
                                    |
 Frame 6                            |                  Frame 2       Frame 2
 --------------->---------------------------------------------->---------->
                                    |
                PRSP                |
                <--------------------

 Frame 1                                          Frame 3 + PREQ     Frame 3
 --------------->---------------------------------------------->---------->

 Frame 2                                               Frame 4       Frame 4
 --------------->---------------------------------------------->---------->
                                                               |
                                                               |
                                    ----------------------------
                                    |
 Frame 3                            |                  Frame 1       Frame 1
 --------------->---------------------------------------------->---------->
                                    |
 Frame 4                            |                  Frame 2       Frame 2
 --------------->---------------------------------------------->---------->
                                    |
                PRSP                |
                <--------------------

                etc.... (steady state reached)

Case 3: Sender uses > half-window
=================================

If we slow the link still further in our thought experiments, we start to see
real flow control coming into play until a steady state is reached.

In this example, NWS=8 and the PRSP crosses with 6 frames owing to round-trip
delay.  The receiver does not increase the NWS because it sees the next PREQ
(just) before each current window is exhausted.

This example takes a while to reach steady state so please be patient!

                Sender                                  Receiver
                ======                                  ========
                PRSP
                <-----------------------------------------------
 Frame 1                                          Frame 1 + PREQ     Frame 1
 --------------->---------------------------------------------->---------->

 Frame 2                                               Frame 2       Frame 2
 --------------->---------------------------------------------->---------->

 Frame 3                                               Frame 3       Frame 3
 --------------->---------------------------------------------->---------->

 Frame 4                                               Frame 4       Frame 4
 --------------->---------------------------------------------->---------->
                                                               |
                                                               |
                                    ----------------------------
                                    |
 Frame 5                            |                  Frame 1       Frame 1
 --------------->---------------------------------------------->---------->
                                    |
 Frame 6                            |                  Frame 2       Frame 2
 --------------->---------------------------------------------->---------->
                                    |
 Frame 7                            |                  Frame 3       Frame 3
 --------------->---------------------------------------------->---------->
                                    |
 Frame 8                            |                  Frame 4       Frame 4
 --------------->---------------------------------------------->---------->
                                    |
 Frame 9                            |                  Next PREQ not received
 --------------->  blocked          |                  so no PRSP sent yet
                                    |
 Frame 10                           |
 --------------->  blocked          |
                                    |
                PRSP                |
                <--------------------

    Frame  9 >> Frame 1 + PREQ                    Frame 5 + PREQ     Frame 5
                ----------------------------------------------->---------->
                                                               |
                                    ----------------------------
                                    |
    Frame 10 >> Frame 2             |                  Frame 1       Frame 1
                ----------------------------------------------->---------->
                                    |
 Frame 3                            |                  Frame 2       Frame 2
 --------------->---------------------------------------------->---------->
                                    |
 Frame 4                            |                  Frame 3       Frame 3
 --------------->---------------------------------------------->---------->
                                    |
 Frame 5                            |                  Frame 4       Frame 4
 --------------->---------------------------------------------->---------->
                                    |
 Frame 6                            |                  Frame 5       Frame 5
 --------------->---------------------------------------------->---------->
                                    |
 Frame 7                            |                  Frame 6       Frame 6
 --------------->---------------------------------------------->---------->
                                    |
 Frame 8                            |                  Frame 7       Frame 7
 --------------->---------------------------------------------->---------->
                                    |
                                    |
                PRSP                |
                <--------------------

 Frame 1                                          Frame 8 + PREQ     Frame 8
 --------------->---------------------------------------------->---------->
                                                               |
                                    ----------------------------
                                    |
 Frame 2                            |                  Frame 1       Frame 1
 --------------->---------------------------------------------->---------->
                                    |
 Frame 3                            |                  Frame 2       Frame 2
 --------------->---------------------------------------------->---------->
                                    |
 Frame 4                            |                  Frame 3       Frame 3
 --------------->---------------------------------------------->---------->
                                    |
 Frame 5                            |                  Frame 4       Frame 4
 --------------->---------------------------------------------->---------->
                                    |
 Frame 6                            |                  Frame 5       Frame 5
 --------------->---------------------------------------------->---------->
                                    |
 Frame 7                            |                  Frame 6       Frame 6
 --------------->---------------------------------------------->---------->
                                    |
                PRSP                |
                <--------------------

 Frame 1                                          Frame 7 + PREQ     Frame 7
 --------------->---------------------------------------------->---------->
                                                               |
                                    ----------------------------
                                    |
 Frame 2                            |                  Frame 1       Frame 1
 --------------->---------------------------------------------->---------->
                                    |
 Frame 3                            |                  Frame 2       Frame 2
 --------------->---------------------------------------------->---------->
                                    |
 Frame 4                            |                  Frame 3       Frame 3
 --------------->---------------------------------------------->---------->
                                    |
 Frame 5                            |                  Frame 4       Frame 4
 --------------->---------------------------------------------->---------->
                                    |
 Frame 6                            |                  Frame 5       Frame 5
 --------------->---------------------------------------------->---------->
                                    |
 Frame 7                            |                  Frame 6       Frame 6
 --------------->---------------------------------------------->---------->
                                    |
                PRSP                |
                <--------------------

                etc.... (steady state reached)

Case 4: Receiver withholds PRSP
==============================

Finally let's look at the case when the receiver delays the PRSP to force
flow control on the sender.

In this example, NWS=8 and the receiver is resource constrained and chooses to
delay the PRSP to flow control the sender.  DWI/HWI are not used in this
example in order to clarify how withholding the PRSP forces pacing.  The
current flow control proposal would allow the receiver to reduce the window
size in addition to or instead of withholding the PRSP.

Note that when it withholds the PRSP the Receiver cannot use the position of the
PREQ within the window to determine whether to increase the window size
(otherwise it would try to increase the available window size precisely when it
is resource constrained!)

                Sender                                  Receiver
                ======                                  ========
                PRSP
                <-----------------------------------------------
 Frame 1                                          Frame 1 + PREQ     Frame 1
 --------------->---------------------------------------------->---------->

 Frame 2                                               Frame 2       Frame 2
 --------------->---------------------------------------------->---------->

 Frame 3                                               Frame 3       Frame 3
 --------------->---------------------------------------------->---------->

 Frame 4                                               Frame 4       Frame 4
 --------------->---------------------------------------------->---------->

                                                       PREQ seen but PRSP
                                                       withheld to force pacing

 Frame 5                                               Frame 5       Frame 5
 --------------->---------------------------------------------->---------->

 Frame 6                                               Frame 6       Frame 6
 --------------->---------------------------------------------->---------->

 Frame 7                                               Frame 7       Frame 7
 --------------->---------------------------------------------->---------->

 Frame 8                                               Frame 8       Frame 8
 --------------->---------------------------------------------->---------->

 Frame 9
 --------------->  blocked

 Frame 10
 --------------->  blocked

                PRSP
                <---------------------------------------------

    Frame  9 >> Frame 1 + PREQ                    Frame 1 + PREQ     Frame 1
                ----------------------------------------------->---------->

    Frame 10 >> Frame 2                                Frame 2       Frame 2
                ----------------------------------------------->---------->

 Frame 3                                               Frame 3       Frame 3
 --------------->---------------------------------------------->---------->

 Frame 4                                               Frame 4       Frame 4
 --------------->---------------------------------------------->---------->

                                                       PREQ seen but PRSP
                                                       withheld to force pacing

 Frame 5                                               Frame 5       Frame 5
 --------------->---------------------------------------------->---------->

 Frame 6                                               Frame 6       Frame 6
 --------------->---------------------------------------------->---------->

 Frame 7                                               Frame 7       Frame 7
 --------------->---------------------------------------------->---------->

 Frame 8                                               Frame 8       Frame 8
 --------------->---------------------------------------------->---------->

 Frame 9
 --------------->  blocked

 Frame 10
 --------------->  blocked

                PRSP
                <---------------------------------------------

                etc...   (steady state reached)

Hopefully that is now precise, though hardly concise!

See you in Raleigh,

Paul Brittain
Data Connection